A network element, such as an Ethernet switch or router, typically operates in “store and forward” mode. In this mode of operations, the network element receives a packet on some “input port”, makes a forwarding decision to decide which output port to send the packet to, and then transmits the packet on the output port. For this network element, transmission is not instantaneous, as a packet that is N bits long sent on an interface that can transmit at K bits per second, will take N/K seconds to transmit. As the packet is being processed for transmission, other packets may be queued for transmission using the same output port. The condition where packets are arriving faster than can be transmitted to some output port is referred to as “network congestion”, or just “congestion.” Network elements typically store packets in a queue in memory. If more memory is available for packet queuing, then the network element can sustain longer bursts of congestion without dropping one or more packets.
However, many Ethernet network elements are built with small buffers, for cost reasons. Furthermore, a high performance network element is commonly implemented using highly integrated silicon, such as a custom application-specific integrated circuit (ASIC) or field-programmable gate array (FPGA). In such a device, adding large memories can be prohibitively costly for many reasons, such as increasing the die-size of the integrated silicon, adding an increased number of off-chip memory interfaces to off-chip memory, and that the off-chip memory runs at slower speeds than the ASIC or FPGA.